home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 103_01 / pack.c < prev    next >
Text File  |  1985-03-09  |  13KB  |  448 lines
  1. /* 18 MAY 81    midnight */
  2. #include "BDSCIO.H"
  3.  
  4. #define        DEBUG        (debug != 0)
  5. int debug;
  6.  
  7. #define     TREEDONE    0
  8. #define        NOT_DONE    -1
  9. #define        HUGE_NO        30000
  10. #define        NUM_CH_TYPES    256
  11. #define        NREAD        4
  12. #define        NELEM        NUM_CH_TYPES*2
  13. #define        NUMSECS        8
  14. #define        ELEMSIZ        8
  15. #define        READ        0
  16. #define        WRITE        1
  17. #define        BOTH        2
  18. #define        NIL        -1    /* nil pointer */
  19. #define        NUL        '\0'
  20. #define        OUTCHAR        '>'
  21.  
  22. int STACK[50];
  23. int *SP;
  24. int OUTBYTE;
  25. int COUNTER;
  26. int BIT;
  27. int C;   /* general purpose to speed things */
  28. int BYTE_DONE;
  29.  
  30. struct ELEMENT 
  31.       { int occur;
  32.     int dad;
  33.     int son_zero;
  34.     int son_one;
  35.       }    tree [NELEM+100];
  36.  
  37. main(argc, argv)
  38. int argc;
  39. char **argv;
  40. {
  41. char tempfile[20], infile [20], outfile [20], s[100];
  42. char arg[30];
  43. int big_daddy;
  44. int i, j;
  45. int nsectors;    /* no. sectors in input file */
  46. int outsecs;    /* no. sectors after encoding file */
  47. int z;
  48.  
  49. debug = FALSE;
  50.  
  51. if (argc == 1)
  52.       { puts("\nThis program compresses a file into an encoded form,");
  53.     puts("\nfor more efficient storage. To 'unpack' and get the");
  54.     puts("\noriginal file back, use UNPACK.COM.");
  55.     puts("\nFormat:        A>pack    infile");
  56.     puts("\n    or        A>pack    infile>outfile");
  57.     puts("\ndefault outfile name is infile.PAK");
  58.     exit();
  59.       }
  60.  
  61. strcpy (tempfile, "TEMPCODE.$$$");
  62. infile[0] = outfile[0] = NUL;
  63. while (--argc > 0)
  64.       { strcpy (arg, *++argv);
  65.     if (OK == strcmp (arg, "-D"))
  66.           { debug = TRUE;
  67.         continue;
  68.           }
  69.  
  70.     if (ERROR != (j = find_char (arg, OUTCHAR)))
  71.           { if (j==0 || j== strlen(arg)-1 )
  72.               { puts("\nNO spaces allowed around output specifier");
  73.             printf("\n%s    is illegal.", arg);
  74.             continue;
  75.               }
  76.         else
  77.               sscanf (arg, "%s>%s", infile, outfile);
  78.           }
  79.     else
  80.           { strcpy (infile, arg);
  81.         if (ERROR != (j = find_char (arg,'.')))
  82.               { for (i=0; i<j; i++)
  83.                 outfile[i] = arg[i];
  84.             outfile[j] = NUL;
  85.               }
  86.         else strcpy (outfile, arg);
  87.         strcat (outfile, ".PAK");
  88.           }
  89.  
  90.     if (ERROR != (j = find_char (outfile,':')))
  91.           {    for (i=0; i<j+1; i++)
  92.             tempfile[i]=outfile[i];
  93.         tempfile[j+1] = NUL;
  94.         strcat(tempfile,"TEMPCODE.$$$");
  95.           }
  96.     if DEBUG printf("\ninfile = <%s>, outfile = <%s>",
  97.                infile,        outfile);
  98.     setmem (tree, NELEM*ELEMSIZ, NIL); /* set all to NIL */
  99.     for (i=0; i<NUM_CH_TYPES*2; i++)    tree[i].occur = 0;
  100.     if (ERROR == (nsectors =  count_occur (infile)))
  101.           { printf("\ncan't construct char. occur. table for <%s>",
  102.                                   infile);
  103.         continue;
  104.           }
  105.     if DEBUG printf("\nnsectors = %d", nsectors);
  106.     big_daddy = generate_tree ();
  107. if DEBUG
  108.       { printf("\nbig_daddy = %d",big_daddy);
  109.     printf("\n\nAnd here's the tree:\n\n");
  110.     puts ("\nHIT AN N TO KILL THIS\n");
  111.     for (z=0; z<NELEM; z++)
  112.         if (tree[z].dad!=NIL || tree[z].occur!=0)
  113.         printf("\n%d    0x%x    %d    %d    %d    %d",z,z,tree[z].occur,tree[z].dad,tree[z].son_one,tree[z].son_zero);
  114.       }
  115.     if (OK != write_occur (tempfile))
  116.           { printf("\nerror writing occurence info to <%s>",tempfile);
  117.         puts ("\nI can't pack this file");
  118.         continue;
  119.           }
  120.     if (OK != set_zero_one (tree))
  121.           { printf("\ncan't pack <%s>",infile);
  122.         continue;
  123.           }
  124.     if (ERROR == (outsecs = encode_file(infile, tempfile,nsectors)))
  125.           { printf("\nerror encoding <%s>", infile);
  126.         continue;
  127.           }
  128.     outsecs+=4;    /* this is for the occurrence info */
  129.     printf("\n%d sectors in <%s>;    %d sectors in <%s>",
  130.         nsectors, infile, outsecs, outfile);
  131.     printf("\nPercent savings is %d",
  132.             (100*(nsectors-outsecs))/nsectors);
  133.     if ( outsecs >= nsectors)
  134.           { printf("\nno savings in packing <%s>",infile);
  135.         unlink (tempfile);
  136.         continue;
  137.           }
  138.     else if (ERROR != open (outfile,READ))
  139.           { printf("\n<%s> already exists",outfile);
  140.         printf("\nShould I erase? (Y/N)");
  141.         if ('Y' != toupper (getchar()))        exit();
  142.         unlink (outfile);
  143.           }
  144.     rename (tempfile, outfile);
  145.     printf("\nencoded form of <%s> is in <%s>", infile, outfile);
  146.       }
  147.  
  148. }
  149.  
  150. /********************************************************************
  151. count # of occurenceds of each character in infile, storing values in
  152. tree structure; return total number sectors in infile, or ERROR
  153. ********************************************************************/
  154. int count_occur (infile)
  155. char *infile;
  156. /*    struct ELEMENT tree[];     is global now */
  157. {
  158. char charbuf [NREAD * SECSIZ];
  159. char *string;
  160. int i, fd, k;
  161. /* int c;   c is global */
  162. int nread, nsectors;
  163.  
  164. k=0;
  165. string=
  166. "zzzz ?snore zzzzzzbuzz click zot foo baz help! forp sniggledorp foobar fripnozzle blod yippeezoo this is a big file WOW\7";
  167.  
  168. if (ERROR == (fd = open (infile, READ)))
  169.       { printf("\nerror opening <%s> in count_occur", infile);
  170.     return (ERROR);
  171.       }
  172.  
  173. printf("<%s>\nand now we pause for station identification\nw",infile);
  174. nsectors = 0;
  175. nread = NREAD;
  176. while (nread == NREAD)
  177.       { setmem (charbuf, NREAD*SECSIZ, NUL);
  178.     nread = read(fd, charbuf, NREAD);
  179.     if (nread==ERROR) {printf("error in count char"); return ERROR;}
  180.     printf("%c",string[k++]);
  181.     if (k>= strlen (string))    k=0;
  182.     nsectors+=nread;
  183.     if DEBUG printf("\n\tnsectors=%d,     nread=%d",
  184.                  nsectors,        nread);
  185.     for (i=0; i < nread*SECSIZ; i++)
  186.           {    if (tree[charbuf[i]].occur++ >30000)
  187.             printf("oi chi wah wah");
  188.           }
  189.  
  190.       }
  191. return (nsectors);
  192. }
  193. /********************************************************************
  194. Generate the tree (backwards) that will be used to encode the file
  195. ********************************************************************/
  196. generate_tree ()
  197. /* struct ELEMENT tree[];  is now global */
  198. {
  199. int daddy, zero, one;
  200. int i, val, nextpapa;
  201.  
  202. daddy = NIL;
  203. nextpapa = NUM_CH_TYPES;
  204. puts("\nnow just be patient, this takes a while....");
  205. while (1)
  206.       { find_lowest ( &one, &zero);
  207.     if (one == NIL && zero == NIL)
  208.         return (daddy);        /* all done; even # char's */
  209.     else if (one == NIL)
  210.         return (zero);        /* all done; odd # chars   */
  211.  
  212.     if ( !(nextpapa%3))    putchar('z');
  213.     daddy = nextpapa++;
  214.     tree[daddy].son_zero = zero;
  215.     tree[daddy].son_one  = one ;
  216.     tree[daddy].occur = tree[zero].occur + tree[one].occur;
  217.     tree[zero].dad = daddy;
  218.     tree[one].dad = daddy;
  219.       }
  220.  
  221. return (daddy);
  222. }
  223.  
  224. /*******************************************************************
  225.     find the two elements with the lowest no. of occurences
  226.     in the file who don't have a daddy yet
  227. *********************************************************************/
  228. int find_lowest (low1, low0)
  229. /* struct ELEMENT tree[];   now global */
  230. int *low1, *low0;
  231. {
  232. int i, l0, l1;
  233. int l0_val, l1_val;
  234.  
  235. l0 = l1 = NIL;
  236. l0_val = l1_val = HUGE_NO;
  237. for (i=0; i<NUM_CH_TYPES*2; i++)
  238.       {
  239.     if ((tree[i].dad == NIL) && (tree[i].occur!=0))
  240.           {
  241.         if (tree[i].occur<l1_val && !(tree[i].occur<l0_val))
  242.               { l1_val = tree[i].occur;
  243.             l1 = i;
  244.               }
  245.         else if (tree[i].occur < l0_val)
  246.               { l1_val = l0_val;
  247.             l0_val = tree[i].occur;
  248.             l1 = l0;
  249.             l0 = i;
  250.               }
  251.           }
  252.       }
  253. *low1 = l1;
  254. *low0 = l0;
  255. }
  256.  
  257. /**********************************************************************
  258.         find character c in string
  259. **********************************************************************/
  260. int find_char (string, c)
  261. char *string, c;
  262. {
  263. char *ptr;
  264. int i;
  265.  
  266. for (i=0; string[i] != NUL; i++)
  267.     if (string[i] == c)    return (i);
  268.  
  269. return (ERROR);
  270. }
  271.  
  272. /********************************************************************
  273.  sets tree[].occur at each active element to 1 or 0 depending  on 
  274.  whether its dad says it's a son_one or a son_zero
  275. *********************************************************************/
  276. int set_zero_one ()
  277. /* struct ELEMENT tree[]; now global */
  278. {
  279. int i, daddy;
  280.  
  281. for (i=0; i<NELEM; i++)
  282.       { if (tree[i].dad == NIL)
  283.         continue;
  284.  
  285.     daddy = tree[i].dad;
  286.     if (tree[daddy].son_zero == i)
  287.         tree[i].occur = 0;
  288.     else if (tree[daddy].son_one == i)
  289.         tree[i].occur = -1;    /* -1 to be used when encoding */
  290.     else
  291.           { printf("\nelement #%d = %c does not ackowledge #%d = %c to be its son",
  292.              daddy, daddy,                i, i);
  293.  
  294.         return (ERROR);
  295.           }
  296.       }
  297. return (OK);
  298. }
  299.  
  300. /***************************